The origins of computers and computer science are rooted in the concepts of algorithms and data structures. To date, the theoretical emphasis has been on the generation and efficient implementation of algorithms. Data structures, which originally included only numbers, were theoretically less well understood although known to be critical to the automation of various mechanical processes. Only recently has a theory of data structures, both as a vehicle to store information and as a tool to solve problems, been recognized and a general methodology of data structures been developed.
The lack of understanding of data structures and their efficient implementation, manipulation and display has led to many difficulties. Perhaps the most important of these difficulties is the almost complete lack of standards for creating and manipulating data structures. Presently, every computer programmer defines and uses his or her own methods for creating and manipulating data structures. Although particular data structures such as binary trees and linked lists have acquired a certain uniformity of style for their creation and manipulation, there is still no standard even for these common data structures.
This non-uniformity has several large costs associated with it. First, as every programmer must create their own data structures separately every time a program is written, a great deal of effort is expended recreating the wheel with each new program. Along with the effort wasted in recreating the data structures, an associated problem is debugging the code creating the data structure every time a new program is written. In addition, as each program is created in a specific operating environment or with a specific operating environment in mind, and programs which operate on one computer may be restricted to only that type of computer. The expense of continually rewriting the same software and the limitations imposed by non-portable software are serious concerns.
This problem also appears in the lack of a consistent and efficient method for implementing abstract container data types and their associated query languages. Examples of container data types include heaps, strings, trees (also called bags), tables, or any combination thereof. These modern data types are naturally used to store and query data, especially when the structure of the data is only partially known or is not known at all.
Container types are the common structures used to create a distinction between object and context, especially at the most primitive levels of distinguishing files from directories. The construction of a query language for bags requires the construction of a container data model, including appropriate operations or methods. The reason for the lack of a natural container model is the difficulty of immediate linguistic self-reference. Most contemporary techniques to solving this difficult problem begin with a naive categorical or first-order query language supporting an atomic or base level set of bag operations, such as singleton formation and additive union, as well as counting and tuple methods. One consequence of the first-order or categorical technique is the inability of the resulting query languages to define, create, or test within themselves certain critically important capabilities such as creating a transitive closure of a multiset, testing a finite graph for acyclicity or connectivity, or testing whether a finite bag has an even number of elements. A second consequence of the first-order or categorical technique is that at some point in the construction it becomes necessary to interpret natural numbers within the query language as a form of self-reference. The commonly adopted solution to this is to move tokens to their exponents and then perform the arithmetic at that level. This type of exponential encoding is not efficient.
Due to the limitations of general first-order logic and the associated categorial views and the innate combinatoric difficulty of the complexity problems involved, many programmers have moved from formally defined methods when addressing this problem of query languages for bags and have retreated to programming with ad hoc engineering solutions. This technique is, of course, incompatible with the goal of universal logic or distributed objects.
What is needed is a standard method and apparatus for creating, manipulating, and displaying data structures and container data types. The structures created should be adaptable to imitate, if not recreate, known data structures, should be flexible enough to describe and manipulate new data structures, and the form of the structures should facilitate operations such as comparison of and addition to the data structures. The apparatus which creates the data structure should also be able to display them in a readily comprehensible format.